package com.wtgroup.demo.mianshi.算法.排序;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 桶排序
 *
 * @author L&J
 * @version 0.0.0
 * @email liuhejun108@163.com
 * @date 2019/9/12 1:15
 */
public class BucketSort {

    public static void sort( Integer[] arr, int bucketNum ) {

        // 计算 max , min, max-min
        int max = arr[0];
        int min = max;
        for ( int i = 1; i < arr.length; i++ ) {
            int e = arr[i];
            if ( e > max ) {
                max = e;
            }else if ( e < min ) {
                min = e;
            }
        }
        int mxmin = max - min;
        int gap    = mxmin / bucketNum + 1;
        // int gap = mxmin / arr.length + 1;
        // int bucketNum = mxmin / gap + 1;
        // System.out.println("gap: " + gap + ", bucketNum: " + bucketNum);
        List<List<Integer>> buckets = new ArrayList<List<Integer>>(bucketNum);
        int initBucketCap = arr.length / bucketNum + 1;     // 每个桶预计平均容量
        for ( int i = 0; i < bucketNum; i++ ) {
            buckets.add(new ArrayList<Integer>(initBucketCap));
        }

        // 遍历元素入桶
        for ( int i = 0; i < arr.length; i++ ) {
            // 定位桶编号
            int bi = (arr[i] - min) / gap;
            buckets.get(bi).add(arr[i]);
        }

        // 对每个桶进行排序
        int j = 0;
        for ( int i = 0; i < buckets.size(); i++ ) {
            List<Integer> list = buckets.get(i);
            // Integer[]     integers = list.toArray(new Integer[]{});
            // MergeSort.sort(integers); // nlog(n)
            Collections.sort(list);

            // 替换到源数组
            for ( int k = 0; k < list.size(); k++ ) {
                arr[j++] = list.get(k);
            }
        }

    }

}
